1. Field of the Invention
The present invention generally relates to a load balancer for a system of computers interconnected by a communications link and having access to a shared data base and, more particularly, to a load balancer which reallocates transaction types between computers of the system by keeping information about lock contention between transaction types so that no excessive overhead is generated in the system when a transaction type is moved from one computer to another. By transaction type, what is meant is all incoming requests that are associated with a program stored in the system that is the embodiment of the transaction. A transaction type is usually identified with a name (i.e., code) to the system by which the association is made to the program.
2. Description of the Prior Art
Transaction processing systems are on-line, application-oriented systems typically implemented on a multi-processor data processing system supporting a plurality of terminals, often distributed over a large geographical area. A typical transaction processing system is IBM's ACP (for Airline Control Program) which, although classically used in airlines reservations systems, has been used in other systems, notably by banks in on-line teller applications. The entire system including computers, terminals, shared data base, communication links and the like, is referred to herein as a system of computers or simply as the system.
High performance transaction processing systems are increasingly used by large organizations. In a typical large installation, thousands of transaction types may be defined, although only a few hundred of them are frequently used. The arrival rate of the commonly used transaction types may fluctuate for various reasons; e.g., seasonally, specific hours of the day, or even randomly. In addition, computers of the system may be added or taken away, or fail. Other applications (program development, other interactive users) may at times demand a bigger share of the system machines.
These environmental changes may seriously overload certain computers of the system and result in a dramatic performance (response time and/or throughput) degradation of certain transaction types running on the overloaded processors. In such a system, it is vital that processing be performed with maximum efficiency. This requires some sort of load balancing among the several computers in the system.
Load balancers are known in the art. Static load balancers are manually tuned by a system operator (a human) who observes how work is apportioned among the computers in a system and, based on his observations, tunes the system in order to even out the load. The balancing is fixed when the system is in operation and thus the system cannot respond to unusual circumstances or changes in the system's usage patterns. If changes are deemed to be necessary, because of failures or slow response times, operator intervention is required and, in the worst case, the system must be shut down while the operator retunes it.
Static allocations for jobs and/or transactions have been proposed in the literature. Characteristics of arriving jobs and the computer systems typically constitute static information. In case some of the system parameters, e.g., the job/transaction arrival rate, vary gradually with time, such parameters may be estimated and used for improved job/transaction routing. Still, rerouting is triggered by human observation and decision. The policy in this case is termed to be quasi-static or quasi-dynamic, as described by A. Kumar and F. Bonomi in "Adaptive Load Balancing in a Heterogeneous Multiserver System with a Central Job Scheduler", Proc. of the 8th Int'l Conf. Distributed Computing Systems, June 1988, pp. 500-508. There are the following varieties of static routing:
1. Probabilistic routing. A fraction of jobs are routed to each computer system according to Bernoulli trials. The probability of being routed to each system is pre-computed to optimize a certain performance measure, such as equalization of processor utilizations at all systems, minimization of the expected overall response time, or equalization of expected response time systems at all systems. The criterion of minimization of the expected overall response time has been considered by J. P. Buzen and P. P. S. Chen, Information Processing 74, pp. 271-175, North Holland, N.Y. (1974), for centralized arrivals, and by A. N. Tantawi and D. Towsley in "Optimal Static Load Balancing in Distributed Computer Systems", Journal of the ACM, 32(2):445-465 (1985), for distributed arrivals. The criterion of equalization of expected response time systems at all systems has been considered by L. Georgiadis, C. Nikolaou and A. Thomasian in "a Fair Workload Allocation Policy for Heterogeneous Systems", IBM T. J. Watson Research Center, RC 14323 (1988). PA1 2. Deterministic routing. In the case of two homogeneous servers, a round-robin routing scheme is optimal, provided that the initial state is identical (e.g., both servers are idle). This is described by A. Ephremides, P. Varaiya and J. Walrand in "A Simple Dynamic routing Problem", IEEE Transactions on Automatic Control, AC-25(4):690-693, August 1982.
Dynamic load balancers have also been proposed that are fully dynamic; i.e., they reassess the need for load balancing after each transaction. Such systems require such a large amount of overhead that they are not practical. In other words, it takes a lot of processor power to implement dynamic load balancing, processor power that would otherwise be devoted to processing the actual transactions. It should be noted that the dynamic load balancers discussed in the literature have not yet been built. In the article by S. P. Yu, S. Balsamo and Y. H. Lee entitled "Notes on Dynamic Load Sharing and Transaction Routing", IBM Research, RC 11537 (1985), a routing decision is made for each message arriving at the distributed system, but these decisions tend to be expensive especially for "short" transactions. P. Krueger and M. Livny in "When is the Best Load Sharing Algorithm a Load Balancing Algorithm?", Computer Sciences Dept., University of Wisconsin, Madison, April 1987, study a variety of algorithms combining a local scheduling policy, such as FIFO (first in, first out) or processor sharing, with a global scheduling policy, such as load sharing and load balancing. If the global scheduling policy is to give work to idling processors, then the policy is one of load sharing, whereas load balancing is performed when the policy is to keep the load of the processors balanced. Several other researchers have proposed dynamic algorithms using the same assumptions. See, for example, M. Livny and M. Melman, "Load Balancing in a Homogeneous Distributed System", Proceedings of the ACM Computer Networks Performance Symposium, April 1982, D. L. Eager, E. D. Lazowska and J. Zahorjan, "Dynamic Load Sharing in Homogeneous Distributed Systems", University of Saskatchewan Tech. Report 84-10-01, October 1984, R. M. Bryant and R. A. Finkel, "A Stable Distributed Scheduling Algorithm", Proc. of the Second International Conf. on Distributed Computing Systems, April 1981, and A. Barak and A. Shiloh, "A Distributed Load-balancing Policy for a Multicomputer", Software-Practice and Experience, 15(9):901-913, September 1985. Some of these algorithms use process pre-emption when performing process migration. This option is not available to use in on-line transaction processing systems. Whereas it may be sensible to pre-empt executing on an overloaded processor and migrate it to an underloaded processor, it is impractical in a transaction environment because of the transaction management overhead.
All of the above work, however, does not address the case of transactions that interfere with each other because of contention. This is an important consideration because even if transactions are routed to processors so that the load generated by their arrival rates is roughly equalized among processors, the overhead generated by data contention may be such that the resulting load is still unbalanced and the overall throughput is greatly reduced.
Static optimization algorithms have been devised to minimize the cost of transaction communication (or interference if the transactions share data) under processor capacity constraints. Examples are described by W. W. Chu, M. Lan and J. Hellerstein, "Estimation of Intermodule Communication (IMC) and its Applications in Distributed Processing Systems", IEEE Transactions on Computers, C-33, August 1984, and P. S. Yu, D. W. Cornell, D. M. Dias, and B. R. Iyer, "Analysis of Affinity Based Routing in Multi-System Data Sharing, IBM Research, RC 11424 (1985). At system generation time, however, statistical information about transaction load and communication is usually not known. In addition, frequent load and configuration changes render the optimization algorithms impractical. Their combinatorial explosion has lead researchers to propose efficient algorithms for special cases. Examples are described by G. S. Rao, H. S. Stone and T.C. Hu in "Assignment of Tasks in a Distributed Processor System with Limited Memory", IEEE Transactions on Computers, C-28(4), April 1979, and H. S. Stone in "Multiprocessor Scheduling with the Aid of Network Flow Algorithms", IEEE Transactions on Software Engineering, SE-3(1), January 1977.
A. Thomasian and P. Bay in "Data Allocation Heuristics for Distributed Systems", Proc. of the EEE INFOCOM 1985, pp. 118-129 (1985), present interchange and clustering heuristics combined with queuing network modelling of a transaction processing system that can yield response time estimates for a specific allocation. A. Dutta, G. Koehler and A. Whinston in "On Optimal Allocation in a Distributed Processing Environment", Management Science, 28(8):839-853, August 1982, start with partial assignments (maps) and augment them by calculating estimated best completion. Clustering of transactions has been proposed by V. B. Gylys and J. A. Edwards in "Optimal Partitioning of Workload for Distributed Systems", Proceedings of COMPCON Fall 1976, (1976), who use centroids, but their algorithm is sensitive to the initial formation of clusters. K. Efe in "Heuristic Models of Task Assignment Scheduling in Distributed Systems", Computer, June 1982, proposes his own clustering algorithm by pairs and assignment algorithm of clusters to processors. S. H. Bokhari in "On the Mapping Problem", IEEE Trans. on Computers, C-30(3), March 1981, presents heuristics (link interchanges) for maximizing the number of edges of the problem graph that are mapped on edges of an array processor. The algorithm appears to work well, although there is no comparison with the optimal assignment. It appears to have special applicability to numerical problems with a periodical problem graph mapped on parallel machines (e.g., NASA's Finite Element Machine).